package com.lx.algorithm.Tree;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;

/**
 * Description:
 * Copyright:   Copyright (c)2019
 * Company:     zefu
 *
 * @author: 张李鑫
 * @version: 1.0
 * Create at:   2021-11-09 21:46:38
 * <p>
 * Modification History:
 * Date         Author      Version     Description
 * ------------------------------------------------------------------
 * 2021-11-09     张李鑫                     1.0         1.0 Version
 */
public class LowestAncestor {
    /**
     * 给一个头节点 跟两个节点 返回这两个节点的最低公共祖先
     */


    public static class Info {
        boolean hasA;
        boolean hasB;
        Node node;

        public Info(boolean hasA, boolean hasB, Node node) {
            this.hasA = hasA;
            this.hasB = hasB;
            this.node = node;
        }
    }


    public static Node lowestAncestor(Node head, Node a, Node b) {
        if (a==b){
            return a;
        }
        return process(head, a, b).node;
    }

    private static Info process(Node head, Node a, Node b) {
        if (head == null) {
            return new Info(false, false, null);
        }
        Info leftInfo = process(head.left, a, b);
        Info rightInfo = process(head.right, a, b);
        Node node = null;
        if (leftInfo.node == null && rightInfo.node == null) {
            boolean hasA = leftInfo.hasA || rightInfo.hasA || head == a;
            boolean hasB = leftInfo.hasB || rightInfo.hasB || head == b;
            if (hasA&&hasB){
                node=head;
            }
            return new Info(hasA,hasB,node);
        }else {
            return leftInfo.node==null?rightInfo:leftInfo;
        }
    }


    // for test
    public static Node generateRandomBST(int maxLevel, int maxValue) {
        return generate(1, maxLevel, maxValue);
    }

    // for test
    public static Node generate(int level, int maxLevel, int maxValue) {
        if (level > maxLevel || Math.random() < 0.5) {
            return null;
        }
        Node head = new Node((int) (Math.random() * maxValue));
        head.left = generate(level + 1, maxLevel, maxValue);
        head.right = generate(level + 1, maxLevel, maxValue);
        return head;
    }

    // for test
    public static Node pickRandomOne(Node head) {
        if (head == null) {
            return null;
        }
        ArrayList<Node> arr = new ArrayList<>();
        fillPrelist(head, arr);
        int randomIndex = (int) (Math.random() * arr.size());
        return arr.get(randomIndex);
    }

    // for test
    public static void fillPrelist(Node head, ArrayList<Node> arr) {
        if (head == null) {
            return;
        }
        arr.add(head);
        fillPrelist(head.left, arr);
        fillPrelist(head.right, arr);
    }

    public static Node lowestAncestor1(Node head, Node o1, Node o2) {
        if (head == null) {
            return null;
        }
        // key的父节点是value
        HashMap<Node, Node> parentMap = new HashMap<>();
        parentMap.put(head, null);
        fillParentMap(head, parentMap);
        HashSet<Node> o1Set = new HashSet<>();
        Node cur = o1;
        o1Set.add(cur);
        while (parentMap.get(cur) != null) {
            cur = parentMap.get(cur);
            o1Set.add(cur);
        }
        cur = o2;
        while (!o1Set.contains(cur)) {
            cur = parentMap.get(cur);
        }
        return cur;
    }


    public static void fillParentMap(Node head, HashMap<Node, Node> parentMap) {
        if (head.left != null) {
            parentMap.put(head.left, head);
            fillParentMap(head.left, parentMap);
        }
        if (head.right != null) {
            parentMap.put(head.right, head);
            fillParentMap(head.right, parentMap);
        }
    }

    public static void main(String[] args) {
//        Node<Integer> node1 = new Node<>(25);
//        Node<Integer> node2 = new Node<>(44);
//        Node<Integer> node3 = new Node<>(98);
//
//        node1.left=node2;
//        node2.right=node3;
//        Node node = lowestAncestor(node1, node1, node2);
//
//        System.out.println(123);

        int maxLevel = 4;
        int maxValue = 100;
        int testTimes = 1000000;
        for (int i = 0; i < testTimes; i++) {
            Node head = generateRandomBST(maxLevel, maxValue);
            Node o1 = pickRandomOne(head);
            Node o2 = pickRandomOne(head);
            if (lowestAncestor1(head, o1, o2) != lowestAncestor(head, o1, o2)) {
                System.out.println("Oops!");
            }
        }
        System.out.println("finish!");
    }


}